class Solution
{
public:
    int numberOfWays(int startPos, int endPos, int k)
    {
        int posDiff = endPos - startPos;
        int stepRemain = k - abs(posDiff);
        if (stepRemain < 0 || stepRemain & 1)
        {
            return 0;
        }
        if (stepRemain == 0)
        {
            return 1;
        }
        int halfRemain = stepRemain / 2;

        // vector<int> steps(k,1);
        // for(int i=0;i<halfRemain;++i)
        // {
        //     steps[i] = -1;
        // }

        // 算steps的全排列，1和-1的个数反过来应该是一样的

        // calcPerm(steps, 0, k-1);
        return calcPermDp(halfRemain, k - halfRemain);
    }

    int permCache[1000][1000] = {0};

    int calcPermDp(int oneCount, int minusOneCount)
    {
        if (oneCount == 0 || minusOneCount == 0)
        {
            return 1;
        }

        if (oneCount > minusOneCount)
        {
            swap(oneCount, minusOneCount);
        }

        if (permCache[oneCount][minusOneCount])
        {
            return permCache[oneCount][minusOneCount];
        }

        int perm = (calcPermDp(oneCount - 1, minusOneCount) + calcPermDp(oneCount, minusOneCount - 1)) % 1000000007;

        permCache[oneCount][minusOneCount] = perm;
        return perm;
    }

    int permCount = 0;

    void calcPerm(vector<int> &v, int beginIndex, int endIndex)
    {
        if (beginIndex == endIndex)
        {
            permCount = (permCount + 1) % 1000000007;
            return;
        }
        for (int i = beginIndex; i <= endIndex; ++i)
        {
            bool calced = false;
            for (int j = beginIndex; j < i; ++j)
            {
                if (v[i] == v[j])
                {
                    calced = true;
                }
            }
            if (calced)
            {
                continue;
            }
            else
            {
                int temp = v[i];
                v[i] = v[beginIndex];
                v[beginIndex] = temp;

                calcPerm(v, beginIndex + 1, endIndex);

                temp = v[i];
                v[i] = v[beginIndex];
                v[beginIndex] = temp;
            }
        }
    }
};